#include "DynamicArray.h"
#include <iostream>
DynamicArray::DynamicArray() : capacity(10), size(0)
{
    this->a = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &array)
{
    capacity = array.capacity;
    size = array.size;
    a = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = array.a[i];
    }
}

void DynamicArray::operator=(const DynamicArray &array)
{
    capacity = array.capacity;
    size = array.size;
    a = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = array.a[i];
    }
}

DynamicArray::~DynamicArray()
{
    delete[] a;
}

void DynamicArray::InsertTail(const ElementType &element)
{
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    a[size++] = element;
}

void DynamicArray::show()
{
    for (int i = 0; i < size; i++)
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
}

int DynamicArray::FindByElemrnt(ElementType element)
{
    for (int i = 0; i < size; i++)
    {
        if (a[i] == element)
            return i;
    }
    return -1;
}

void DynamicArray::RemoveByIndex(ElementType index)
{
    if (index < 0 || index > size)
    {
        std::cout << "插入位置非法!\n";
        return;
    }
    for (int i = index; i < size; i++)
    {
        a[i] = a[i + 1];
    }
    size--;
}

void DynamicArray::RemoveByElement(ElementType element)
{
    for (int i = 0; i < size; i++)
    {
        if (a[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 快速排序 : 双指针 + 递归
void DynamicArray::FastSort(int start, int end)
{
    if (start >= end) // 终止条件
        return;
    int left = start;
    int right = end;
    int temp = a[left]; // 将最左边的值定为基准值
    while (left < right)
    {
        // 右边往左动，找比基准值小的数
        while (a[right] > temp && left < right)
            right--;
        if (left < right)
            a[left++] = a[right]; // 把右边比基准值小的数扔到左边

        // 左边往右动，找比基准值大的数
        while (a[left] < temp && left < right)
            left++;
        if (left < right)
            a[right--] = a[left]; // 把左边比基准值大的数扔到右边
    }
    a[left] = temp;
    FastSort(start, left - 1);
    FastSort(right + 1, end);
}

int DynamicArray::BinarySearch(int element)
{
    int left = 0;
    int right = size - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (a[mid] > element)
            right = mid - 1;
        else if (a[mid] < element)
            left = mid + 1;
        else
            return mid;
    }
    return -1;
}